map 和 unordered_map的区别和实现机制

1. map

• 基于 红黑树 ： std::map 基于一种 自平衡的二叉搜索树 （通常是红黑树）实现，可以保持元素有序。
• 有序 容器：元素按照键的顺序自动排序，可以通过键值进行有序遍历。
• 元素访问：提供对元素的快速查找、插入和删除操作，时间复杂度为 O(log n) 。
• 唯一 键：每个键都是唯一的，不允许有重复的键。
• 迭代器稳定性 ：由于基于树结构，迭代器在遍历时是稳定的，即使容器发生插入或删除操作，迭代器指向的元素也不会改变，除非该元素被删除。

1. unordered_map

• 基于 哈希表 ： std::unordered_map 基于哈希表实现，通过哈希函数将键分布到数组的槽位中。
• 无序 容器：元素在容器中是无序的，不能按键的顺序进行遍历。
• 元素访问：理想情况下，提供平均时间复杂度为 O(1) 的快速查找、插入和删除操作。最坏情况下，性能可能下降到 O(n) 。
• 允许重复键：实际上， std::unordered_map 不允许有重复的键，因为哈希表的设计不允许两个元素具有相同的哈希值。如果发生哈希冲突，会通过某种方式（如链表或开放寻址）解决。
• 迭代器稳定性：由于基于哈希表，迭代器的稳定性不如 std::map 。在发生哈希表的重新哈希 （rehashing） 时，迭代器可能会失效。
• 遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的。

1. 使用场景

• 当需要元素有序且对性能有较高要求时，应选择 **std::map** 。
• 当元素的顺序不重要，且需要快速访问元素时，应选择 **std::unordered_map** 。

1. 实现机制

• std::map 的实现依赖于红黑树的旋转和颜色变换来保持树的平衡，确保操作的时间复杂度。
• std::unordered_map 的实现依赖于一个良好的哈希函数来最小化冲突，并通过**解决冲突的机制（如链表或开放寻址）**来存储具有相同哈希值的元素。